Dining cryptographers problem
In cryptography, the dining cryptographers problem studies how to perform a secure multi-party computation of the boolean-OR function. David Chaum first proposed this problem in 1988, and used it as an illustrative example to show it was possible to send anonymous messages with unconditional sender and recipient untraceability. Despite the word "dining", the dining cryptographers problem is unrelated to the dining philosophers problem. Description Three cryptographers gather around a table for dinner. The waiter informs them that the meal has been paid by someone, who could be one of the cryptographers or the National Security Agency (NSA). The cryptographers respect each other's right to make an anonymous payment, but want to find out whether the NSA paid. So they decide to execute a two-stage protocol. In the first stage, every two cryptographers establish a shared one-bit secret, say by tossing a coin behind a menu. Suppose, after the coin tossing, cryptographer A and B share a secret bit 1 , A and C share 0 , and B and C share 1 . In the second stage, each cryptographer publicly announces a bit, which is the Exclusive OR (XOR) of the shared bits he holds if he didn't pay the meal, or the opposite of the XOR if he paid. Suppose none of the cryptographers paid, then A would announce 1 \oplus 0 = 1 , B would announce 1 \oplus 1 = 0 , and C would announce 0 \oplus 1 = 1 . On the other hand, if A paid, he would announce \lnot{(1 \oplus 0)} = 0 . After the second stage is the truth revealing. One simply performs XOR of all the announced bits. If the result is 0, then it implies that none of the cryptographers paid (so NSA must have paid). Otherwise, it would imply one of the cryptographers paid, but his identity remains unknown to the other cryptographers. The above protocol was named by David Chaum as the Dining Cryptographers network, or DC-net. Limitations The DC-net protocol is simple and elegant. It, however, has several limitations. 1. Collision - If two cryptographers paid the dinner, their messages will cancel each other out, and the final XOR result will be 0 . This is called a collision. In a more general case, a collision happens as long as any even number of participants send messages. The measure suggested by David Chaum is to re-transmit the message once a collision is detected, but the paper does not explain exactly how to arrange the re-transmission. 2. Disruption - The cryptographer who last announces the bit has the advantage of manipulating the final result. For example, if he is dishonest, he can jam the protocol so that the final XOR result is always 0 . This problem occurs because the original protocol was designed without using any public key technology; but as a downside, the protocol lacks reliable mechanisms to check whether participants honestly follow the protocol. 3. Complexity - The protocol requires pair-wise shared secret keys between the participants, which may be problematic if there are many participants. Also, though the DC-net protocol is "unconditionally secure", it actually depends on the assumption that "unconditionally secure" channels already exist between pairs of the participants, which is not easy to achieve in practice. All of the above limitations are addressed in the Anonymous veto network solution. References * Category:Cryptography Category:Mathematical problems ja:食事する暗号学者の問題